package cn.edu.jxau.test;

import java.util.Arrays;

import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Stack;

/**
 * 即时Dijkstra算法构造最短路径树(shotest path tree)
 * @author 付大石
 */
public class DiligentDijkstra {

    public static void main(String[] args) {

        DirectedGraph g = new DirectedGraph(8);
        g.addEdge(new DirectedEdge(4, 5, 0.35));
        g.addEdge(new DirectedEdge(5, 4, 0.35));
        g.addEdge(new DirectedEdge(4, 7, 0.37));
        g.addEdge(new DirectedEdge(5, 7, 0.28));
        g.addEdge(new DirectedEdge(7, 5, 0.28));
        g.addEdge(new DirectedEdge(5, 1, 0.32));
        g.addEdge(new DirectedEdge(0, 4, 0.38));
        g.addEdge(new DirectedEdge(0, 2, 0.26));
        g.addEdge(new DirectedEdge(7, 3, 0.39));
        g.addEdge(new DirectedEdge(1, 3, 0.29));
        g.addEdge(new DirectedEdge(2, 7, 0.34));
        g.addEdge(new DirectedEdge(6, 2, 0.40));
        g.addEdge(new DirectedEdge(3, 6, 0.52));
        g.addEdge(new DirectedEdge(6, 0, 0.58));
        g.addEdge(new DirectedEdge(6, 4, 0.93));
        System.out.println(g);
        int s = 0;
        DiligentDijkstra spt = new DiligentDijkstra(g, s);
        for (int v = 0; v < g.v(); v++) {
            if (spt.hasPathTo(v)) {
                System.out.printf("%d to %d:", s, v);
                for (DirectedEdge edge : spt.pathTo(v)) {
                    System.out.printf("%d->%d(%.2f)\t", edge.from(), edge.to(), edge.weight());
                }
                System.out.println();
            } else {
                System.out.println("没有到达" + v + "的路径");
            }
        }
    }

    /**
     * 路径
     */
    private DirectedEdge edgeTo[];

    /**
     * 距离(权重)
     */
    private double[] distTo;

    public DiligentDijkstra(DirectedGraph g, int s) {

        if (s < 0 || s >= g.v()) {
            throw new IllegalArgumentException("图中不存在顶点s=" + s);
        }
        edgeTo = new DirectedEdge[g.v()];
        distTo = new double[g.v()];
        Arrays.fill(distTo, Double.POSITIVE_INFINITY);

        IndexMinPQ<Double> minPQ = new IndexMinPQ<>(g.v());
        distTo[s] = 0;
        minPQ.insert(s, 0.0);
        while (!minPQ.isEmpty()) {
            relax(g, minPQ, minPQ.delMin());
        }
        if(!check(g,s)) {
            throw new RuntimeException("Dijkstra算法构造SPT失败");
        }
    }

    /**
     * @param g
     * @param from
     */
    private void relax(DirectedGraph g, IndexMinPQ<Double> minPQ, int from) {

        for (DirectedEdge edge : g.adj(from)) {
            int to = edge.to();
            if (distTo[to] > edge.weight() + distTo[from]) { // relax
                edgeTo[to] = edge;
                distTo[to] = edge.weight() + distTo[from];
                minPQ.insert(to, distTo[to]);
            }
        }
    }

    /**
     * 检测Dijkstra算法构造的SPT是否正确
     * @param g
     * @param s
     * @return
     */
    private boolean check(DirectedGraph g, int s) {

        // 图中不能有负权重的边 //
        for (DirectedEdge edge : g.edges()) {
            if (edge.weight() < 0) {
                return false;
            }
        }

        // 检测distTo,edgeTo的值是否符合逻辑 //
        if (distTo[s] != 0 || edgeTo[s] != null) { // 出发点的distTo[],edgeTo[]是否为初值
            return false;
        }
        for (int i = 0, end = g.v(); i < end; i++) {
            if (i == s) {
                continue;
            }
            if (edgeTo[i] == null && distTo[i] < Double.POSITIVE_INFINITY) {
                return false;
            }
            if (distTo[i] == Double.POSITIVE_INFINITY && edgeTo[i] != null) {
                return false;
            }
        }

        // 满足distTo[w] == distTo[v] + e.weight() //
        for (int i = 0, end = g.v(); i < end; i++) {
            DirectedEdge edge = edgeTo[i];
            if (edge == null) {
                continue;
            }
            int from = edge.from();
            int to = edge.to();
            if (to != i) {
                return false;
            }
            if (distTo[to] != distTo[from] + edge.weight()) {
                return false;
            }
        }
        return true;
    }

    public double distTo(int to) {
        return distTo[to];
    }

    public boolean hasPathTo(int to) {
        return distTo[to] < Double.POSITIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int to) {

        Stack<DirectedEdge> path = new LinkedStack<>();
        if (!hasPathTo(to)) {
            return path;
        }
        while (edgeTo[to] != null) {
            path.push(edgeTo[to]);
            to = edgeTo[to].from();
        }
        return path;
    }
}
